{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find And Replace in String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findReplaceString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串中的查找与替换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你会得到一个字符串 <code>s</code>&nbsp;(索引从 0 开始)，你必须对它执行 <code>k</code> 个替换操作。替换操作以三个长度均为 <code>k</code> 的并行数组给出：<code>indices</code>,&nbsp;<code>sources</code>,&nbsp;&nbsp;<code>targets</code>。</p>\n",
    "\n",
    "<p>要完成第 <code>i</code> 个替换操作:</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>检查 <strong>子字符串</strong> &nbsp;<code>sources[i]</code>&nbsp;是否出现在 <strong>原字符串</strong> <code>s</code> 的索引&nbsp;<code>indices[i]</code>&nbsp;处。</li>\n",
    "\t<li>如果没有出现，&nbsp;<strong>什么也不做</strong>&nbsp;。</li>\n",
    "\t<li>如果出现，则用&nbsp;<code>targets[i]</code>&nbsp;<strong>替换</strong>&nbsp;该子字符串。</li>\n",
    "</ol>\n",
    "\n",
    "<p>例如，如果 <code>s = \"abcd\"</code>&nbsp;，&nbsp;<code>indices[i] = 0</code> ,&nbsp;<code>sources[i] = \"ab\"</code>， <code>targets[i] = \"eee\"</code> ，那么替换的结果将是 <code>\"<u>eee</u>cd\"</code> 。</p>\n",
    "\n",
    "<p>所有替换操作必须 <strong>同时</strong> 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间<strong>不会重叠 </strong>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，一个 <code>s = \"abc\"</code> ，&nbsp; <code>indices = [0,1]</code> ， <code>sources = [\"ab\"，\"bc\"]</code>&nbsp;的测试用例将不会生成，因为 <code>\"ab\"</code> 和 <code>\"bc\"</code> 替换重叠。</li>\n",
    "</ul>\n",
    "\n",
    "<p><em>在对 <code>s</code>&nbsp;执行所有替换操作后返回 <strong>结果字符串</strong> 。</em></p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中连续的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/12/833-ex1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\", indices = [0,2], sources = [\"a\",\"cd\"], targets = [\"eee\",\"ffff\"]\n",
    "<strong>输出：</strong>\"eeebffff\"\n",
    "<strong>解释：\n",
    "</strong>\"a\" 从 s 中的索引 0 开始，所以它被替换为 \"eee\"。\n",
    "\"cd\" 从 s 中的索引 2 开始，所以它被替换为 \"ffff\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong><img src=\"https://assets.leetcode.com/uploads/2021/06/12/833-ex2-1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\", indices = [0,2], sources = [\"ab\",\"ec\"], targets = [\"eee\",\"ffff\"]\n",
    "<strong>输出：</strong>\"eeecd\"\n",
    "<strong>解释：\n",
    "</strong>\"ab\" 从 s 中的索引 0 开始，所以它被替换为 \"eee\"。\n",
    "\"ec\" 没有从<strong>原始的</strong> S 中的索引 2 开始，所以它没有被替换。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>k == indices.length == sources.length == targets.length</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= indices[i] &lt; s.length</code></li>\n",
    "\t<li><code>1 &lt;= sources[i].length, targets[i].length &lt;= 50</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "\t<li><code>sources[i]</code> 和 <code>targets[i]</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-and-replace-in-string](https://leetcode.cn/problems/find-and-replace-in-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-and-replace-in-string](https://leetcode.cn/problems/find-and-replace-in-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"\\n[0, 2]\\n[\"a\", \"cd\"]\\n[\"eee\", \"ffff\"]', '\"abcd\"\\n[0, 2]\\n[\"ab\",\"ec\"]\\n[\"eee\",\"ffff\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S, indexes, sources, targets):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type indexes: List[int]\n",
    "        :type sources: List[str]\n",
    "        :type targets: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        shift =0 \n",
    "        data = sorted(zip(indexes,sources,targets))\n",
    "        for i in range(len(data)):\n",
    "            [index,source,target]=data[i]\n",
    "            #print(S[indexes[i]+shift:indexes[i]+len(sources[i])+shift],sources[i])\n",
    "            if S[index+shift:index+len(source)+shift] == source:\n",
    "                S=S[:index+shift]+target+S[index+len(source)+shift:]\n",
    "                shift+=len(target)-len(source)\n",
    "        return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S, indexes, sources, targets):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type indexes: List[int]\n",
    "        :type sources: List[str]\n",
    "        :type targets: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        from collections import defaultdict\n",
    "        ddict=defaultdict(tuple)\n",
    "        for i in range(len(indexes)):\n",
    "            ddict[indexes[i]]=(sources[i],targets[i])\n",
    "        \n",
    "        res=\"\"\n",
    "        st=0\n",
    "        while st<len(S):\n",
    "            if st not in ddict:\n",
    "                res+=S[st]\n",
    "                st+=1\n",
    "            elif st+len(ddict[st][0])-1>=len(S) or S[st:(st+len(ddict[st][0]))]!=ddict[st][0]:\n",
    "                res+=S[st]\n",
    "                st+=1\n",
    "            else:\n",
    "                res+=ddict[st][1]\n",
    "                st+=len(ddict[st][0])\n",
    "        return res\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: 'str', indexes: 'List[int]', sources: 'List[str]', targets: 'List[str]') -> 'str':\n",
    "        \n",
    "        dic = dict([])#创建一个空的列表字典\n",
    "        n = len(indexes)\n",
    "        for i in range(n):\n",
    "            dic[indexes[i]] = i \n",
    "        indexes.sort()\n",
    "        j = n - 1\n",
    "        while j >= 0:  # 从右往左替换\n",
    "            pos = indexes[j]\n",
    "            ind = dic[pos]\n",
    "            if(S.find(sources[ind], pos) == pos): # //如果sources[ind]出现在指定位置，则替换\n",
    "                S = S[0:pos] + targets[ind] + S[pos+len(sources[ind]):] \n",
    "            j -= 1\n",
    "        return S        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S, indexes, sources, targets):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type indexes: List[int]\n",
    "        :type sources: List[str]\n",
    "        :type targets: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        lenS, S = len(S), list(S)\n",
    "        \n",
    "        for i, x, y in sorted(zip(indexes, sources, targets), reverse = True):\n",
    "            if all(i + k < lenS and S[i + k] == x[k] for k in range(len(x))):\n",
    "                S[i: i + len(x)] = list(y)\n",
    "                \n",
    "        return \"\".join(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S, indexes, sources, targets):\n",
    "        dex=0\n",
    "        while True:\n",
    "            try:\n",
    "                if S[indexes[dex]:indexes[dex]+len(sources[dex]):]!=sources[dex]:\n",
    "                    indexes=indexes[:dex:]+indexes[dex+1::]\n",
    "                    sources=sources[:dex:]+sources[dex+1::]\n",
    "                    targets=targets[:dex:]+targets[dex+1::]\n",
    "                else:\n",
    "                    dex+=1\n",
    "            except:\n",
    "                break\n",
    "        if not indexes:\n",
    "            return S\n",
    "        lst=[(indexes[i],targets[i],len(sources[i])) for i in range(len(indexes))]\n",
    "        lst=sorted(lst,key=lambda x: x[0])\n",
    "        ldex=0\n",
    "        rdex=lst[0][0]-1\n",
    "        result=[]\n",
    "        for i in range(len(indexes)-1):\n",
    "            print(ldex,rdex)\n",
    "            result.append(S[ldex:rdex+1:])\n",
    "            result.append(lst[i][1])\n",
    "            #print(S[rdex+1::])\n",
    "            ldex=rdex+lst[i][2]+1\n",
    "            rdex=lst[i+1][0]-1\n",
    "        i=len(indexes)-2\n",
    "        result.append(S[ldex:rdex + 1:])\n",
    "        result.append(lst[i+1][1])\n",
    "        ldex = rdex + lst[i+1][2] + 1\n",
    "        #print(result)\n",
    "        result.append(S[ldex::])\n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        S = list(S)\n",
    "        for i, x, y in sorted(zip(indexes, sources, targets), reverse = True):\n",
    "            if all(i+k < len(S) and S[i+k] == x[k] for k in range(len(x))):\n",
    "                S[i:i+len(x)] = list(y)\n",
    "\n",
    "        return \"\".join(S)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        #利用一个新字符串记录就可以了\n",
    "        #什么垃圾题，indexes乱序\n",
    "        sorted_indexes = sorted(range(len(indexes)), key=lambda k: indexes[k])\n",
    "        indexes = [indexes[i] for i in sorted_indexes]\n",
    "        sources = [sources[i] for i in sorted_indexes]\n",
    "        targets = [targets[i] for i in sorted_indexes]\n",
    "\n",
    "\n",
    "        ans=S[:indexes[0]]\n",
    "        for i,idx in enumerate(indexes):\n",
    "            if S[idx:idx+len(sources[i])]==sources[i]:\n",
    "                ans=ans+targets[i]\n",
    "                if i<len(indexes)-1:\n",
    "                    ans=ans+S[idx+len(sources[i]):indexes[i+1]]\n",
    "                else:\n",
    "                    ans=ans+S[idx+len(sources[i]):]\n",
    "            else:\n",
    "                if i<len(indexes)-1:\n",
    "                    ans=ans+S[idx:indexes[i+1]]\n",
    "                else:\n",
    "                    ans=ans+S[idx:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        #利用一个新字符串记录就可以了\n",
    "        #什么垃圾题，indexes乱序\n",
    "        sorted_indexes = sorted(range(len(indexes)), key=lambda k: indexes[k])\n",
    "        indexes = [indexes[i] for i in sorted_indexes]\n",
    "        sources = [sources[i] for i in sorted_indexes]\n",
    "        targets = [targets[i] for i in sorted_indexes]\n",
    "\n",
    "\n",
    "        ans=S[:indexes[0]]\n",
    "        for i,idx in enumerate(indexes):\n",
    "            if S[idx:idx+len(sources[i])]==sources[i]:\n",
    "                ans=ans+targets[i]\n",
    "                if i<len(indexes)-1:\n",
    "                    ans=ans+S[idx+len(sources[i]):indexes[i+1]]\n",
    "                else:\n",
    "                    ans=ans+S[idx+len(sources[i]):]\n",
    "            else:\n",
    "                if i<len(indexes)-1:\n",
    "                    ans=ans+S[idx:indexes[i+1]]\n",
    "                else:\n",
    "                    ans=ans+S[idx:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        S = list(S)\n",
    "        l = len(S)\n",
    "        for i, s, t in sorted(zip(indexes, sources, targets), reverse=True):\n",
    "            k = len(s)\n",
    "            if i+k-1 < l and S[i:i+k] == list(s):\n",
    "                S[i:i+k] = list(t)\n",
    "        return \"\".join(S)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        tmp = 0\n",
    "        sav = copy.deepcopy(indexes)\n",
    "        sav.sort()\n",
    "        for t in sav:\n",
    "            i=indexes.index(t)\n",
    "            index = indexes[i] + tmp\n",
    "            if len(S) - index >= len(sources[i]) and S[index:index + len(sources[i])] == sources[i]:\n",
    "                S = S[:index] + targets[i] + S[index + len(sources[i]):]\n",
    "                tmp += len(targets[i]) - len(sources[i])\n",
    "        return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findReplaceString(self, S, indexes, sources, targets):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type indexes: List[int]\n",
    "        :type sources: List[str]\n",
    "        :type targets: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        d = {}\n",
    "        for iidx, sidx in enumerate(indexes):\n",
    "            d[sidx] = iidx\n",
    "\n",
    "        cur_S = 0\n",
    "        res = []\n",
    "        for idx in sorted(d.keys()):\n",
    "            i = d[idx]\n",
    "            if cur_S < idx:\n",
    "                res.append(S[cur_S:idx])\n",
    "                cur_S = idx\n",
    "            \n",
    "            l = len(sources[i])\n",
    "            if S[cur_S:cur_S+l] == sources[i]:\n",
    "                res.append(targets[i])\n",
    "            else:\n",
    "                res.append(S[cur_S:cur_S+l])\n",
    "            \n",
    "            cur_S = idx + l\n",
    "        \n",
    "        if cur_S < len(S):\n",
    "            res.append(S[cur_S:len(S)])\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        a = []\n",
    "        for m in range(len(indexes)):\n",
    "            a.append([indexes[m],sources[m],targets[m]])\n",
    "        a = sorted(a,key=lambda x:x[0])\n",
    "        k = 0\n",
    "        for j in range(len(a)):\n",
    "            i = a[j][0] + k\n",
    "            if S[i:i+len(a[j][1])] == a[j][1]:\n",
    "                S = S[0:i] + a[j][2] + S[i+len(a[j][1]):]\n",
    "                k += (len(a[j][2]) - len(a[j][1]))\n",
    "        return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        need_replace = []\n",
    "        for i in range(len(indexes)):\n",
    "            l_source = len(sources[i])\n",
    "            if S[indexes[i]: indexes[i] + l_source] == sources[i]:\n",
    "                need_replace.append([indexes[i], l_source, targets[i]])\n",
    "        need_replace = sorted(need_replace, key = lambda x: x[0])\n",
    "        print(need_replace)\n",
    "        res = ''\n",
    "        cur = 0\n",
    "        for p in need_replace:\n",
    "            if p[0] > cur:\n",
    "                res += S[cur:p[0]]\n",
    "            res += p[2]\n",
    "            cur = p[0] + p[1]\n",
    "        return res + S[cur:]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        count = 0\n",
    "        ss = S\n",
    "        l = []\n",
    "        for i, s, t in zip(indexes, sources, targets):\n",
    "            if s == ss[i:min(i+len(s), len(ss))]:\n",
    "                l.append([count, i, i+len(s)])\n",
    "            count += 1\n",
    "        print(l)\n",
    "        l = sorted(l, key=lambda x: -x[1])\n",
    "        for indx, b, e in l:\n",
    "            ss = ss[:b] + targets[indx] + ss[e:]\n",
    "        return ss\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        z=sorted(list(zip(indices,sources,targets)))\n",
    "        cnt=0\n",
    "        for pos,old,new in z:\n",
    "            if s[pos+cnt:pos+cnt+len(old)]==old:\n",
    "                s=s[:pos+cnt]+new+s[pos+cnt+len(old):]\n",
    "                cnt+=len(new)-len(old)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        z = zip(indices, sources, targets)\n",
    "        z = sorted(z, key=lambda x: x[0], reverse=True)\n",
    "        for ind, source, target in z:\n",
    "            if s[ind:ind + len(source)] == source:\n",
    "                s = s[:ind] + target + s[ind + len(source):]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        data = zip(indices, sources, targets)\n",
    "        sortedDate = sorted(data, key=lambda x: x[0])\n",
    "        indices, sources, targets = zip(*sortedDate)\n",
    "\n",
    "        substringList = []\n",
    "        preIndex = 0\n",
    "        for i in range(len(indices)):\n",
    "            substringList.append(s[preIndex: indices[i]])\n",
    "\n",
    "            if s[indices[i]: indices[i]+len(sources[i])] == sources[i]:\n",
    "                substringList.append(targets[i])\n",
    "                preIndex = indices[i] + len(sources[i])\n",
    "            else:\n",
    "                preIndex = indices[i]\n",
    "        substringList.append(s[preIndex: len(s)])\n",
    "\n",
    "        return \"\".join(substringList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        # 有两种方法，后面有备注\n",
    "        map ={}\n",
    "        for i,chr in enumerate(s):\n",
    "            map[i]= chr\n",
    "        for ind,source,target in zip(indices,sources,targets):\n",
    "            if s.find(source,ind)==ind:\n",
    "                map[ind]=target\n",
    "                for _ in range(len(source)-1):\n",
    "                    map.pop(ind+1)\n",
    "                    ind += 1\n",
    "        ind_map = list(map.keys())\n",
    "        ans =''\n",
    "        for ind in ind_map:\n",
    "            ans += map[ind]\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        d = [-1] * n\n",
    "        for i, (j, source) in enumerate(zip(indices, sources)):\n",
    "            if s[j: j + len(source)] == source:\n",
    "                d[j] = i\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if d[i] >= 0:\n",
    "                ans.append(targets[d[i]])\n",
    "                i += len(sources[d[i]])\n",
    "            else:\n",
    "                ans.append(s[i])\n",
    "                i += 1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        for i, sou, tar in sorted(list(zip(indices, sources, targets)), reverse=True):\n",
    "            l = len(sou)\n",
    "            if s.startswith(sou, i):\n",
    "                s = s[:i] + tar + s[i + l:]\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\r\n",
    "        n=len(indices)\r\n",
    "        ops=sorted(range(n),key=lambda x:indices[x])\r\n",
    "        ret=[]\r\n",
    "        idx=0\r\n",
    "        for op in ops:\r\n",
    "            indice=indices[op]\r\n",
    "            pat=sources[op]\r\n",
    "            tar=targets[op]\r\n",
    "            l=len(pat)\r\n",
    "            if s[indice:indice+l]==pat:\r\n",
    "                ret.append(s[idx:indice])\r\n",
    "                ret.append(tar)\r\n",
    "                idx=indice+l\r\n",
    "        ret.append(s[idx:])\r\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        k = len(indices)\n",
    "        for i in range(k-1):\n",
    "            for j in range(k-i-1):\n",
    "                if indices[j] > indices[j+1]:\n",
    "                    indices[j], indices[j+1] = indices[j+1],indices[j]\n",
    "                    sources[j], sources[j+1] = sources[j+1],sources[j]\n",
    "                    targets[j], targets[j+1] = targets[j+1], targets[j]\n",
    "\n",
    "        ans = ''\n",
    "        i,j = 0,0\n",
    "        while i < len(s):\n",
    "            if j == k or i != indices[j]:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            if sources[j] == s[i:i+len(sources[j])]:\n",
    "                ans += targets[j]\n",
    "                i += len(sources[j])\n",
    "            else:\n",
    "                if not (j+1 < k and indices[j+1] == i):\n",
    "                    ans += s[i]\n",
    "                    i += 1\n",
    "            j += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        m, n = len(s), len(indices)\n",
    "        res = \"\"\n",
    "\n",
    "        pre = 0\n",
    "        for idx, source, target in sorted(zip(indices, sources, targets)):\n",
    "            res += s[pre: idx]\n",
    "            # check match\n",
    "            j, k = idx, 0\n",
    "            while k < len(source) and j < len(s) and s[j] == source[k]:\n",
    "                j += 1\n",
    "                k += 1\n",
    "            if k == len(source):\n",
    "                res += target\n",
    "                pre = idx + k\n",
    "            else:\n",
    "                # note s[pre: idx] gets added though not match\n",
    "                # pre still needs to be updated\n",
    "                pre = max(pre, idx)\n",
    "        else:\n",
    "            res += s[pre:]\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
